#include <cstdio>
#define mod 1000000007

int prime[ 3402 ], primec;
bool visit[ 31623 ];

void calprime( )
{
    int i, j;
    for ( i = 2; i <= 31623; i++ )
    {
        if ( !visit[ i ] )
        {
            prime[ primec++ ] = i;
            for ( j = i * 2; j <= 31623; j += i )
                visit[ j ] = 1;
        }
    }
}

long long euler( int n )
{
    int i;
    long long ret = n;
    for ( i = 0; prime[ i ] * prime[ i ] <= n && i < primec; i++ )
        if ( n % prime[ i ] == 0 )
        {
            ret = ret * ( prime[ i ] - 1 ) / prime[ i ];
            while ( n % prime[ i ] == 0 )
                n /= prime[ i ];
        }
    if ( n != 1 )
        ret = ret * ( n - 1 ) / n;
    return ret;
}

long long calc( int n, long long m )
{
    int p = 1;
    if ( n == 1 ) return 0;
    long long a[ 2 ][ 2 ], b[ 2 ][ 2 ], c[ 2 ][ 2 ];
    a[ 0 ][ 0 ] = 0; a[ 1 ][ 0 ] = 1;
    a[ 0 ][ 1 ] = m - 2; a[ 1 ][ 1 ] = m - 3;
    b[ 0 ][ 0 ] = b[ 1 ][ 1 ] = 1; b[ 0 ][ 1 ] = b[ 1 ][ 0 ] = 0;
    n -= 2;
    while ( p <= n ) p <<= 1;
    p >>= 1;
    while ( p )
    {
        c[ 0 ][ 0 ] = ( b[ 0 ][ 0 ] * b[ 0 ][ 0 ] + b[ 0 ][ 1 ] * b[ 1 ][ 0 ] ) % mod;
        c[ 0 ][ 1 ] = ( b[ 0 ][ 0 ] * b[ 0 ][ 1 ] + b[ 0 ][ 1 ] * b[ 1 ][ 1 ] ) % mod;
        c[ 1 ][ 0 ] = ( b[ 1 ][ 0 ] * b[ 0 ][ 0 ] + b[ 1 ][ 1 ] * b[ 1 ][ 0 ] ) % mod;
        c[ 1 ][ 1 ] = ( b[ 1 ][ 0 ] * b[ 0 ][ 1 ] + b[ 1 ][ 1 ] * b[ 1 ][ 1 ] ) % mod;
        b[ 0 ][ 0 ] = c[ 0 ][ 0 ]; b[ 0 ][ 1 ] = c[ 0 ][ 1 ]; b[ 1 ][ 0 ] = c[ 1 ][ 0 ]; b[ 1 ][ 1 ] = c[ 1 ][ 1 ];
        if ( p & n )
        {
            c[ 0 ][ 0 ] = ( b[ 0 ][ 0 ] * a[ 0 ][ 0 ] + b[ 0 ][ 1 ] * a[ 1 ][ 0 ] ) % mod;
            c[ 0 ][ 1 ] = ( b[ 0 ][ 0 ] * a[ 0 ][ 1 ] + b[ 0 ][ 1 ] * a[ 1 ][ 1 ] ) % mod;
            c[ 1 ][ 0 ] = ( b[ 1 ][ 0 ] * a[ 0 ][ 0 ] + b[ 1 ][ 1 ] * a[ 1 ][ 0 ] ) % mod;
            c[ 1 ][ 1 ] = ( b[ 1 ][ 0 ] * a[ 0 ][ 1 ] + b[ 1 ][ 1 ] * a[ 1 ][ 1 ] ) % mod;
            b[ 0 ][ 0 ] = c[ 0 ][ 0 ]; b[ 0 ][ 1 ] = c[ 0 ][ 1 ]; b[ 1 ][ 0 ] = c[ 1 ][ 0 ]; b[ 1 ][ 1 ] = c[ 1 ][ 1 ];
        }
        p >>= 1;
    }
    return ( ( m - 2 ) * ( m - 1 ) % mod * b[ 0 ][ 0 ] % mod + ( ( m - 2 ) * ( m - 1 ) % mod ) * ( m - 3 ) % mod * b[ 1 ][ 0 ] % mod ) % mod;
}

long long extgcd( long long a, long long b, long long &x, long long &y )
{
    if ( b == 0 ) { x = 1; y = 0; return a; }
    long long d = extgcd( b, a % b, x, y );
    long long t = x; x = y; y = t - a / b * y;
    return d;
}

int main( )
{
    int n, k, i;
    long long x, y;
    long long ans;
    calprime( );
    while ( scanf("%d%d", &n, &k) != EOF )
    {
        ans = 0;
        for ( i = 1; i * i < n; i++ )
            if ( n % i == 0 )
            {
                ans = ( ans + euler( n / i ) * calc( i, k ) % mod ) % mod;
                ans = ( ans + euler( i ) * calc( n / i, k ) % mod ) % mod;
            }
        if ( i * i == n )
            ans = ( ans + euler( i ) * calc( i, k ) % mod ) % mod;
        ans = ans * k % mod;
        extgcd( n, mod, x, y );
        x = ( x + mod ) % mod;
        ans = ans * x % mod;
        printf("%I64d\n", ans);
    }
    return 0;
}
